package leetcode.t6Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author K
 * @date 2024/1/30 9:18
 */
public class T94_InorderTraversal {

    /**
     * 4 2 5 1 6 3 7
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        TreeNode cur = root;
        dfs(cur, result);
        return result;
    }


    private static void dfs(TreeNode cur, ArrayList<Integer> result) {
        if (cur != null) {
            dfs(cur.left, result);
            result.add(cur.val);
            dfs(cur.right, result);
        }
    }

    /**
     * 4 2 5 1 6 3 7
     */
    public static List<Integer> stackInorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        //一直遍历到左树节点，完了在遍历右树节点
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode node = stack.pop();
            result.add(node.val);
            cur = node.right;
        }

        return result;
    }

    /**
     * 1 2 4 5 3 6 7
     */
    public static List<Integer> stackPreorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        //一直遍历到左树节点，完了在遍历右树节点
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                result.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode node = stack.pop();
            cur = node.right;
        }

        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;

        // *    1
        // *  2   3
        // * 4 5 6 7
        List<Integer> integers = inorderTraversal(root);
        List<Integer> integers1 = stackInorderTraversal(root);
        List<Integer> integers2 = stackPreorderTraversal(root);
        System.out.println();
    }

}
